package top.codetheory._05_二叉搜索树;

import top.codetheory._05_二叉搜索树.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author:
 * @since: 2023/12/14 14:21
 **/
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> root;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal(BinarySearchTree.Visitor<E> visitor) {
        if (visitor == null) return;
        preorderTraversal(root, visitor);
    }

    private void preorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;  // 防止进行递归
        visitor.stop = visitor.visit(node.element);
        preorderTraversal(node.left, visitor);
        preorderTraversal(node.right, visitor);
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root, visitor);
    }

    private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;  // 防止继续进行递归
        inorderTraversal(node.left, visitor);
        if (visitor.stop) return;           // 这里判断的意义, 防止stop的值被覆盖, 一旦发现是true, 不走下面的代码
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);
    }

    /**
     * 中序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(root, visitor);
    }

    private void postorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null|| visitor.stop) return;  // 防止继续进行递归
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        if (visitor.stop) return;                // 这里判断的意义, 防止stop的值被覆盖, 一旦发现是true, 不走下面的代码
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) {  // 如果传过来的是true, 则停止遍历
                return;
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 通过递归的方式获取二叉树的高度
     * @return
     */
    public int heightByRecursion() {
        return heightByRecursion(root);  // 二叉树的高度就是根节点的高度
    }

    /**
     * 通过递归的方式获取某个节点的高度
     * @param root
     * @return
     */
    private int heightByRecursion(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(heightByRecursion(node.left), heightByRecursion(node.right));  // 某个节点的高度等于1 + 左/右子树的高度
    }

    /**
     * 通过层序遍历计算树的高度
     * @return
     */
    public int heightByLevelOrderTraversal() {
        Queue<Node<E>> queue = new LinkedList<>();

        queue.offer(root);
        int height = 0;  // 记录树的高度
        int levelSize = 1;  // 记录每层有多少个元素

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) {  // 如果levelSize == 0 , 说明这一层的元素已经访问完了
                levelSize = queue.size();  // 此时队列里面的都为下一层的元素, 赋值给levelSize
                height++;  // 高度加一
            }

        }
        return height;
    }

    public boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();

            if (isLeaf && !node.isLeaf()) {  // 要求是叶子节点, 但是node不是叶子节点
                return false;
            }

            if (node.left != null) {
                queue.offer(node.left);
            } else if(node.right != null) {  // 左空右不空
                return false;
            }

            if (node.right != null) { // 右不空
                queue.offer(node.left);
            } else {  // 左不空右空 || 左空右空
                isLeaf = true;   //  说明后面的节点都是叶子节点
            }
        }
        return true;
    }
    /**
     * 通过前序遍历反转二叉树
     */
    public void reverseTreeByPreorderTraversal() {
        reverseTreeByPreorderTraversal(root);
    }

    /**
     * 通过前序遍历反转指定节点
     *
     * @param node
     */
    private void reverseTreeByPreorderTraversal(Node<E> node) {
        if (node == null) return;
        reverseLeftAndRightNode(node);
        reverseTreeByPreorderTraversal(node.left);
        reverseTreeByPreorderTraversal(node.right);
    }

    /**
     * 通过中序遍历反转二叉树
     * @return
     */
    public void reverseTreeByInorderTraversal() {
        reverseTreeByInorderTraversal(root);
    }

    /**
     * 通过中序遍历反转指定节点
     *
     * @param node
     */
    private void reverseTreeByInorderTraversal(Node<E> node) {
        if (node == null) return;
        reverseTreeByInorderTraversal(node.left);
        reverseLeftAndRightNode(node);  // 因为当代码执行到这里的时候, 左右已经发生了改变, 所以下面还是left
        reverseTreeByInorderTraversal(node.left);
    }

    /**
     * 通过中序遍历反转二叉树
     * @return
     */
    public void reverseTreeByPostorderTraversal() {
        reverseTreeByPostorderTraversal(root);
    }

    /**
     * 通过中序遍历反转指定节点
     *
     * @param node
     */
    private void reverseTreeByPostorderTraversal(Node<E> node) {
        if (node == null) return;
        reverseTreeByPostorderTraversal(node.left);
        reverseTreeByPostorderTraversal(node.right);
        reverseLeftAndRightNode(node);
    }

    /**
     * 通过层序遍历反转反转二叉树
     * @param node
     * @return
     */
    public void reverseTreeByLevelOrderTraversal() {
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> curr = queue.poll();

            reverseLeftAndRightNode(curr);

            if (curr.left != null) {
                queue.offer(curr.left);
            }
            if (curr.right != null) {
                queue.offer(curr.right);
            }
        }
    }

    /**
     * 交换node的左右两个节点
     * @param node
     */
    private void reverseLeftAndRightNode(Node<E> node) {
        Node<E> temp = node.left;
        node.left = node.right;
        node.right = temp;
    }


    /**
     * 找到当前节点的前驱节点
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        Node<E> p = node.left;
        if (p != null) {  // 前驱节点在左子树的情况, 有左子树
            while (p.right != null) {  // 一直往右找, 知道p.right为null
                p = p.right;
            }
            return p;  // 此时p就是要找的前驱节点
        }
        while (node.parent != null && node == node.parent.left) {  // 没有前驱节点, 那么就去找他的父节点, 有父节点, 且当前节点是父节点的左节点
            node = node.parent;
        }
        // 此时退出循环, 有两种情况, 1. node.parent 为null, 那么返回null, 也就是node.parent
        // 2. 当前节点不是父节点的左节点, 那么就是相当于找到了, 返回node.parent
        return node.parent;

    }
    /**
     * 找到当前节点的后继节点
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;
        Node<E> s = node.right;
        if (s != null) {
            while (s.left != null) {
                s = s.left;
            }
            return s;
        }
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;

    }


    protected Node<E> createNode(E element, Node<E> parent) {
        return new Node<>(element, parent);
    }
    public static abstract class Visitor<E>{  // 从接口变为抽象类的原因: 应为接口里面不能定义变量, 而我们需要一个变量存储停止遍历的flag

        boolean stop; // true 代表停止, false 代表继续

        /**
         *
         * @param element
         * @return 如果返回true, 就带表停止遍历
         */
        public abstract boolean visit(E element);
    }

    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 判断是否为叶子节点
         * @return
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 判断是否有两个子节点
         * @return
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        /**
         * 判断自己是否是父节点的左子树
         * @return 自己是否是父节点的左子树
         */
        public boolean isLeftChildren() {
            return parent != null && this == parent.left;
        }

        /**
         * 判断自己是否是父节点的右子树
         * @return 自己是否是父节点的左子树
         */
        public boolean isRightChildren() {
            return parent != null && this == parent.right;
        }

        /**
         * 获取兄弟节点
         * @return 兄弟节点
         */
        public Node<E> sibling() {
            if (isLeftChildren()) {
                return parent.right;
            }
            if (isRightChildren()) {
                return parent.left;
            }
            return null;  // 意味着没有父节点, 那也就没有兄弟节点, 返回null
        }

        /**
         * 获取叔父节点
         * @return 叔父节点
         */
        public Node<E> uncle() {
            return parent.sibling();  // 叔父节点就是父节点的兄弟节点
        }
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }
}